home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / minix / update~3.z / update~3 / lib_qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-09-05  |  6.7 KB  |  264 lines
  1. /*
  2.  * qsort - parts adapted from Doug Schmidt's sort challenge posting
  3.  *       thanks Doug
  4.  *
  5.  *        ++jrb    bammi@dsrgsun.ces.cwru.edu
  6.  */
  7.  
  8. #if (defined(minix) || defined(unix))
  9. #  include <sys/types.h>
  10. #  ifdef minix
  11. #    include "lib.h"
  12. #  endif
  13. #else
  14. #  include <stddef.h>
  15. #  include <stdlib.h>
  16. #endif
  17. #include <string.h>
  18.  
  19. #ifdef __GNUC__
  20. #  ifdef minix
  21.      void *alloca(unsigned long);
  22.      typedef unsigned long size_t;
  23. #  else
  24. #    define alloca __builtin_alloca
  25. #  endif
  26. #  define INLINE inline
  27. #else
  28. #  define INLINE /* */
  29. #endif
  30.  
  31.     
  32.     /* the next 4 #defines implement a very fast in-line stack abstraction */
  33.     
  34. #define MAKE_STACK(S) \
  35.     ((stack_node *) alloca((size_t)(sizeof(stack_node) * (S))))
  36. #define PUSH(LOW,HIGH) \
  37.     top->lo = LOW; top->hi = HIGH; top++
  38. #define POP(LOW,HIGH) \
  39.     --top; LOW = top->lo; HIGH = top->hi
  40. #define STACK_NOT_EMPTY \
  41.     (stack < top)                
  42.  
  43. static void swap(unsigned char *, unsigned char *, size_t);
  44. static void move(unsigned char *, unsigned char *, size_t);
  45. static void insert_sort(void *, void *, size_t, int (*)());
  46. static void *find_pivot(void *, void *, size_t, int (*)());
  47.  
  48.  
  49.  
  50. /* Discontinue quicksort algorithm when partition gets below this size. */
  51.  
  52. #ifndef MAX_THRESH
  53. #define MAX_THRESH 15
  54. #endif
  55.  
  56. /* Data structure for stack of unfulfilled obligations. */
  57. typedef struct 
  58. {
  59.     void *lo;
  60.     void *hi;
  61. } stack_node;
  62.  
  63. static void *scratch;    /* scratch mem */
  64.  
  65. /* swap two elements of size n each */
  66. INLINE static void swap(a, b, n)
  67. unsigned char *a, *b;
  68. size_t n;
  69. {
  70.     unsigned char t;
  71.     while(n--)
  72.     {
  73.     t    = *a;
  74.         *a++ = *b;
  75.     *b++ = t;
  76.     }
  77. }
  78.  
  79.  
  80. /* move src to dest */
  81. INLINE static void Move(src, dst, n)
  82. unsigned char *src, *dst;
  83. size_t n;
  84. {
  85.     while(n--)
  86.     *dst++ = *src++;
  87. }
  88.  
  89.  
  90. /* Once main array is partially sorted by quicksort the remainder is 
  91.    completely sorted using insertion sort, since this is efficient 
  92.    for partitions below MAX_THRESH size. BASE points to the beginning 
  93.    of the array to sort, and END_PTR points at the very last element in
  94.    the array (*not* one beyond it!). */
  95.  
  96. INLINE static void 
  97.     insert_sort(void *base, void *end_ptr, size_t siz, int (*cmp)())
  98. {
  99.     void *run_ptr;
  100.     void *tmp_ptr = end_ptr;
  101.     void *temp = scratch;
  102.  
  103.     /* Find the largest element in the array and put it at the 
  104.        end of the array.  This acts like a sentinel, and it speeds
  105.        up the inner loop of insertion sort. */
  106.  
  107.     for (run_ptr = end_ptr - siz; run_ptr >= base; run_ptr -= siz)
  108.     if ((*cmp)(run_ptr, tmp_ptr) > 0) 
  109.         tmp_ptr = run_ptr;
  110.  
  111.     if(tmp_ptr != end_ptr)
  112.     { swap (tmp_ptr, end_ptr, siz); }
  113.  
  114.     /* Typical insertion sort, but we run from the `right-hand-side'
  115.        downto the `left-hand-side.' */
  116.     
  117.     for (run_ptr = end_ptr - siz; run_ptr > base; run_ptr -= siz) 
  118.     {
  119.     tmp_ptr = run_ptr - siz;
  120.     Move(tmp_ptr, temp, siz);
  121.  
  122.     /* Select the correct location for the new element, 
  123.        by sliding everyone down by 1 to make room! */
  124.     
  125.     while ((*cmp)(temp , (tmp_ptr += siz)) > 0)
  126.         Move(tmp_ptr, (tmp_ptr - siz), siz);
  127.  
  128.     Move(temp, tmp_ptr - siz, siz);
  129.     }
  130. }
  131.  
  132. /* Return the median value selected from among the 
  133.    LOW, MIDDLE, and HIGH.  Rearrange LOW and HIGH so
  134.    the three values are sorted amongst themselves. 
  135.    This speeds up later work... */
  136.  
  137. INLINE static void *
  138.     find_pivot(void *low, void *high, size_t siz, int (*cmp)())
  139. {
  140.     void *middle = low + (((high - low)/siz) >> 1) * siz;
  141.     
  142.     if ((*cmp)(middle, low) < 0)
  143.     { swap (middle, low, siz); }
  144.     if ((*cmp)(high, middle) < 0)
  145.     { swap (middle, high, siz); }
  146.     else 
  147.     return middle;
  148.     
  149.     if ((*cmp)(middle, low)  < 0)
  150.     { swap (middle, low, siz); }
  151.     
  152.     return middle;
  153. }
  154.  
  155. /* Order elements using quicksort.  This implementation incorporates
  156.    4 optimizations discussed in Sedgewick:
  157.    
  158.    1. Non-recursive, using an explicit stack of log (n) pointers that 
  159.    indicate the next array partition to sort.
  160.    
  161.    2. Choses the pivot element to be the median-of-three, reducing
  162.    the probability of selecting a bad pivot value.
  163.    
  164.    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
  165.    insertion sort to sort within the partitions.  This is a
  166.    big win, since insertion sort is faster for small, mostly
  167.    sorted array segements.
  168.    
  169.    4. The larger of the 2 sub-partitions are always pushed onto the
  170.    stack first, with the algorithm then concentrating on the
  171.    smaller partition.  This *guarantees* no more than log (n)
  172.    stack size is needed! */
  173.  
  174. void qsort(base, total_elems, size, cmp)
  175. void *base;
  176. size_t total_elems;
  177. size_t size;
  178. int (*cmp)();
  179. {
  180.     if (total_elems > 1)
  181.     {
  182.     void        *lo;
  183.     void        *hi;
  184.     void        *left_ptr;
  185.     void        *right_ptr;
  186.     void        *pivot;
  187.     size_t        Thresh = MAX_THRESH * size;
  188.     stack_node  *stack;
  189.     stack_node  *top;  
  190.     size_t max_stack_size = 1;
  191.  
  192.     /* Calculate the exact stack space required in the worst case.
  193.        This is approximately equal to the log base 2 of TOTAL_ELEMS. */
  194.     
  195.     {   size_t i;    /* this helps the compiler */
  196.         for (i = 1; i < total_elems; i += i) 
  197.             max_stack_size++;
  198.     }
  199.     /* Create the stack, or die trying! */
  200.     if (stack = MAKE_STACK (max_stack_size))
  201.         top = stack;
  202.     else
  203.         return;
  204.  
  205.     /* allocate scratch */
  206.     if((scratch = alloca(size)) == (void *)0)
  207.         return;    /* die */
  208.     
  209.     lo = base;
  210.     hi = lo + (total_elems - 1) * size;
  211.  
  212.     do {
  213.         next: if((hi - lo) <= Thresh)
  214.         {
  215.         insert_sort(lo, hi, size, cmp);
  216.         if(STACK_NOT_EMPTY)
  217.             {  POP(lo, hi); goto next; }
  218.         else
  219.             break;
  220.         }
  221.         /* otherwise next iteration of qsort */
  222.         /* Select the median-of-three here. This allows us to
  223.            skip forward for the LEFT_PTR and RIGHT_PTR. */
  224.         pivot = find_pivot (lo, hi, size, cmp);
  225.         left_ptr  = lo + size;
  226.         right_ptr = hi - size; 
  227.  
  228.         /* Here's the famous ``collapse the walls'' section of
  229.            quicksort.  Gotta like those tight inner loops! */
  230.         do { /* partition loop */
  231.         while ((*cmp)(left_ptr, pivot) <= 0) /* see knuth for <= */
  232.             left_ptr += size;
  233.         
  234.         while ((*cmp)(pivot, right_ptr) <= 0)
  235.             right_ptr -= size;
  236.         
  237.         if (left_ptr < right_ptr) 
  238.                 {
  239.             swap (left_ptr, right_ptr, size);
  240.             left_ptr += size;
  241.             right_ptr -= size;
  242.                 }
  243.         else if (left_ptr == right_ptr) 
  244.                 {
  245.             left_ptr +=size; 
  246.             right_ptr -= size; 
  247.             break;
  248.                 }
  249.             } while (left_ptr <= right_ptr);
  250.         
  251.         if ((right_ptr - lo) > (hi - left_ptr)) 
  252.             {                   /* push larger left table */
  253.         PUSH (lo, right_ptr);
  254.         lo = left_ptr;
  255.             }
  256.         else 
  257.             {                   /* push larger right table */
  258.         PUSH (left_ptr, hi);
  259.         hi = right_ptr;
  260.             }
  261.         } while(1);    /* when stack is empty it'll break out */
  262.     } /* if total_elems > 1 */
  263. }
  264.